package BFS;

import java.util.*;

/**
 * Created with Intellij IDEA.
 * Description;
 * User:TQ02
 * Data:2024-03-11
 * Time:14:38
 * Text：675. 为高尔夫比赛砍树
 */
public class Texts3 {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Queue<String> q = new LinkedList<>();
        Set<String> set = new HashSet<>();
        Set<String> hash = new HashSet<>();
        for(String s : wordList)
        {
            set.add(s);
        }
        if(!set.contains(endWord)) return 0;
        if(beginWord.equals(endWord)) return 1;
        int size=beginWord.length();
        int ret=1;
        q.add(beginWord);
        //hit" -> "hot" -> "dot" -> "dog" -> "cog"
        while(!q.isEmpty())
        {
            ret++;
            int l=q.size();
            while(l-->0) {
                String str = q.poll();
                for (int i = 0; i < size; i++) {
                    char[] array = str.toCharArray();
                    for (int k = 0; k < 26; k++) {
                        char a = (char) ('a' + k);
                        array[i] = a;
                        String next = new String(array);
                        if (set.contains(next) && !hash.contains(next)) {
                            if (next.equals(endWord))
                                return ret;
                            q.add(next);
                            hash.add(next);
                        }
                    }
                }
            }
        }
        return 0;
    }
    public static void main(String[] args) {
        Texts3 t1=new Texts3();
        String[] array={"hot","dot","dog","lot","log","cog"};
        List<String> t2=new ArrayList<>();
        for( String a: array)
        {
            t2.add(a);
        }
        System.out.println(t1.ladderLength("hit","cog",t2));
    }
}
